import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-14
 * Time: 21:48
 */
public class Solution {
    //前缀和:用数组存储前1,2,3,..i项的和
    // 哈希表:存储前n项的和以及对应的下标
    //主要思路:0换为-1
    //求前i项和,如果sum和之前的出现相同的说明这之间的区间是满足范围的
    public int findMaxLength(int[] nums) {
        for(int i=0;i<nums.length;i++){
            if(nums[i]==0){
                nums[i]=-1;
            }
        }
        int maxLength=0;
        int sum=0;
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,-1);
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            if(map.containsKey(sum)){
                //哈希表里面已经出现过了
                int prevIndex=map.get(sum);
                if(prevIndex==-1){
                    maxLength=i+1;
                }else{
                    maxLength=Math.max(maxLength,i-prevIndex);
                }
            }else{
                map.put(sum,i);
            }
        }
        return maxLength;
    }
}
